#include <stdio.h>
#include <malloc.h>

/* program to reverse a linked list */

typedef struct node Node;

struct node{
	int data;
	Node *next;
};

Node *newNode(int);
Node *reverseLinkedList(Node *);
Node *recursiveReverseLinkedList(Node *);
int printLinkedList(Node *);

int main(){
	Node *head;
	head = newNode(1);
	head->next = newNode(2);
	head->next->next = newNode(3);
	printLinkedList(head);
	
	head = recursiveReverseLinkedList(head);
	printLinkedList(head);
	printf("\n--Reversing LinkedList--\n");
	return 0;
}

Node *newNode(int data){
	Node *newnode = (Node*)malloc(sizeof(Node));
	newnode->data = data;
	newnode->next = NULL;
	return newnode;
}

int printLinkedList(Node *head){
	while(head){
		printf("\nNode value: %d", head->data);
		head = head->next;
	}
	return 0;
}

Node *reverseLinkedList(Node *head){
	Node *root = head;
	Node *prev = NULL;
	Node *current = head;
	Node *next;
	while(current){
		next = current->next;
		current->next = prev;
		prev = current;
		current = next;
	}
	//*head = prev;
	return prev;
}

Node *recursiveReverseLinkedList(Node *head){
	/* incorrect because we cannot put the head reference at the end */
	if(!head){
		return NULL;
	}
	Node *first = head;
	Node *rest = head->next;
	if(!rest){	
		return NULL;
	}
	rest = recursiveReverseLinkedList(rest);
	first->next->next = first;
	first->next = NULL;
	
	return rest;
}
